UVa/10986 - Sending email/10986.cpp

   1 /*
   2 Problem: 10986 - Sending email (UVa Online Judge)
   3 Andrés Mejía-Posada (http://github.com/andmej/acm)
   4
   5 Verdict: Accepted
   6 Algorithm: Dijkstra's
   7
   8 */
   9 #include <iostream>
  10 #include <algorithm>
  11 #include <queue>
  12
  13 using namespace std;
  14
  15 struct edge{
  16   int to, weight;
  17   edge() {}
  18   edge(int t, int w) : to(t), weight(w) {}
  19   bool operator < (const edge &that) const {
  20     return weight > that.weight;
  21   }
  22 };
  23
  24 int main(){
  25   int N, C=0;
  26   scanf("%d", &N);
  27   while (N-- && ++C){
  28     int n, m, s, t;
  29     scanf("%d %d %d %d", &n, &m, &s, &t);
  30     vector<edge> g[n];
  31     while (m--){
  32       int u, v, w;
  33       scanf("%d %d %d", &u, &v, &w);
  34       g[u].push_back(edge(v, w));
  35       g[v].push_back(edge(u, w));
  36     }
  37
  38     int d[n];
  39     for (int i=0; i<n; ++i) d[i] = INT_MAX;
  40     d[s] = 0;
  41     priority_queue<edge> q;
  42     q.push(edge(s, 0));
  43     while (q.empty() == false){
  44       int node = q.top().to;
  45       int dist = q.top().weight;
  46       q.pop();
  47
  48       if (dist > d[node]) continue;
  49       if (node == t) break;
  50
  51       for (int i=0; i<g[node].size(); ++i){
  52         int to = g[node][i].to;
  53         int w_extra = g[node][i].weight;
  54
  55         if (dist + w_extra < d[to]){
  56           d[to] = dist + w_extra;
  57           q.push(edge(to, d[to]));
  58         }
  59       }
  60     }
  61     printf("Case #%d: ", C);
  62     if (d[t] < INT_MAX) printf("%d\n", d[t]);
  63     else printf("unreachable\n");
  64   }
  65   return 0;
  66 }